minimum area tree
→ Kruskal method
The Kruskal method is O(E log E)
When E is too big to make it in time
The PRIM method, in combination with the Fibonacci heap, gives an O(E+V log V)
Even with a naive binary heap we get O((E+V)log V)
O(E) if E can be sorted in linear time.
→ linear time sort
---
This page is auto-translated from /nishio/最小全域木. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.